#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //先搜索第一列
        int index = -1;
        for(int i = 0;i<matrix.size();++i){
            if(matrix[i][0]>=target){
                index = i;
                break;
            }
        }
        //二分查找
        if(index<0){
            //对最后一行进行搜索
            return func(matrix[matrix.size()-1],target);
        }
        else if((index-1)<0){
            if(matrix[index][0]==target){
                return true;
            }
            return false;
        }
        else if(index-1>=0){
            //对某一行进行二分查找
            if(matrix[index][0]==target){
                return true;
            }
            return func(matrix[index-1],target);
        }
        return false;
    }
    bool func(vector<int>& V,int target){
        int left = 0;
        int right = V.size()-1;
        while(left<=right){
            int mid = (left+right)/2;
            if(V[mid]==target){
                return true;
            }
            else if(V[mid]>target){
                right = mid-1;
            }
            else if(V[mid]<target){
                left = mid+1;
            }
        }
        return false;
    }
};

int main(){
    Solution S;
    vector<vector<int>> nums = {{1,3,5,7},{10,11,16,20},{23,30,34,60},{23,30,34,60}};
    cout<<S.searchMatrix(nums,13)<<endl;
}